package huaweiod.first;

import java.util.HashMap;
import java.util.Map;

/**
 * 华为OD机试真题 Java 实现【挑选字符串】【2022.11 Q4 新题】
 */
public class A_2023_33_SelectString {

    public static int selectString(String A, String B) {
        Map<Character, Integer> position = new HashMap<>();
        for (int i = 0; i < B.length(); i++) {
            position.put(B.charAt(i), i);
        }

        int[] res = new int[B.length()];
        for (int i = 0; i < A.length(); i++) {
            if(position.containsKey(A.charAt(i))) {
                int po = position.get(A.charAt(i));
                if(po == 0 || res[po - 1] > res[po]) {
                    res[po]++;
                }
            }
        }
        return res[B.length() - 1];
    }

    public static void main(String[] args) {
        System.out.println(selectString("bbadcac","bac"));
    }
}
